package structs;

/**
 * 链表测试
 *
 * @author panshao
 * @CREATE 2019/5/23
 */
public class ListTest {

    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        ListNode listNode_2 = new ListNode(2);
        ListNode listNode_3 = new ListNode(3);
        ListNode listNode_4 = new ListNode(4);
        ListNode listNode_5 = new ListNode(5);
        listNode.setNext(listNode_2);
        listNode_2.setNext(listNode_3);
        listNode_3.setNext(listNode_4);
        listNode_4.setNext(listNode_5);
        //listNode_5.setNext(listNode_3);

       /* ListNode reverse = reverse(listNode);
        System.out.println("reverse1 = [" + reverse.getVal() + "]");
        System.out.println("reverse2 = [" + reverse.getNext().getVal() + "]");
        System.out.println("reverse3 = [" + reverse.getNext().getNext().getVal() + "]");*/

        /*Boolean delDesNode = delDesNode(listNode, 2);
        int i = 0;
        while (listNode != null){
            System.out.println("reverse"+ i++ +" = [" + listNode.getVal() + "]");
            listNode = listNode.getNext();
        }*/

       /* detectCircle(listNode);*/

        ListNode listNode_1_1 = new ListNode(1);
        ListNode listNode_1_2 = new ListNode(2);
        ListNode listNode_1_3 = new ListNode(4);
        ListNode listNode_2_1 = new ListNode(1);
        ListNode listNode_2_2 = new ListNode(3);
        ListNode listNode_2_3 = new ListNode(4);
        listNode_1_1.setNext(listNode_1_2);
        listNode_1_2.setNext(listNode_1_3);

        listNode_2_1.setNext(listNode_2_2);
        listNode_2_2.setNext(listNode_2_3);

        ListNode listNode1 = mergeTwoLists(listNode_1_1, listNode_2_1);

    }

    /**
     * 单链表反转
     * @param srcList
     * @return
     */
    public static ListNode reverse(ListNode srcList){
        ListNode temp = null;
        ListNode sourceList = srcList;
        while (sourceList != null){
            ListNode next = sourceList.getNext();
            sourceList.setNext(temp);
            temp = sourceList;
            sourceList = next;
        }
        return temp;
    }

    /**
     * 检测是否有环
     * @param sourceList
     * @return
     */
    public static Boolean detectCircle(ListNode sourceList){
        ListNode fast = sourceList;
        ListNode slow = sourceList;
        while (fast != null && fast.getNext() != null){
            fast = fast.getNext().getNext();
            slow = slow.getNext();
            if(fast.getVal() == slow.getVal()){
                return true;
            }
        }
        return false;
    }

    /**
     * 两个有序的链表合并
     * @param oneList
     * @param twoList
     * @return
     */
    public static ListNode combined(ListNode oneList, ListNode twoList){
        boolean oneLong = true;
        ListNode tempOne = oneList;
        ListNode tempTwo = twoList;
        // 找出长链表
        while(tempOne != null || tempTwo != null){
            if(tempOne == null){
                oneLong = false;
                break;
            }
            if(tempTwo == null){ break;}
            tempOne = tempOne.getNext();
            tempTwo = tempTwo.getNext();
        }
        ListNode tempLong = oneList;
        ListNode tempShort = twoList;
        if(!oneLong){
            tempLong = twoList;
            tempShort = oneList;
        }

        while (tempShort != null){
            while (tempLong != null){
                ListNode nextLong = null;
                if(tempShort.getVal() > tempLong.getVal() && tempShort.getVal() < tempLong.getNext().getVal()){
                    nextLong = tempLong.getNext().getNext();
                }else{
                    nextLong = tempLong.getNext();
                }

                tempLong = nextLong;
            }
            ListNode nextShort = tempShort.getNext();
            tempShort = nextShort;
        }
        return tempLong;
    }

    /**
     * 删除链表倒数第n个结点
     * @param srcList
     * @param n
     * @return
     */
    public static Boolean delDesNode(ListNode srcList, int n){
        ListNode temp = srcList;
        int size = 0;
        while(temp != null){
            size++;
            temp = temp.getNext();
        }
        // 计算正数的位置,index为删除节点的上一个位置
        int index = size - n;

        temp = srcList;
        Boolean deleted = false;
        int i = 0;
        while(temp != null){
            i++;
            if(index == i){
                temp.setNext(temp.getNext().getNext());
                deleted = true;
                break;
            }
            temp = temp.getNext();
        }

        return deleted;
    }

    /**
     * 求链表的中间节点
     * @param srcList
     * @return
     */
    public static ListNode getMiddleNode(ListNode srcList){
        // 求出链表长度

        // 找出中间节点

        return null;
    }

    /**
     * 合并两个有序链表
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode ret = new ListNode(0);
        ListNode temp = ret;

        while(l1 != null && l2 != null){
            if(l1.val <= l2.val) {
                temp.next = l1;
                l1 = l1.next;
            }else{
                temp.next = l2;
                l2 = l2.next;
            }
            temp = temp.next;
        }

        if(l1 != null){
            temp.next = l1;
        }

        if(l2 != null){
            temp.next = l2;
        }

        ret = ret.next;

        return ret;
    }
}
